/**
 * @author LKQ
 * @date 2022/2/22 20:05
 * @description 二分查找，定义cnt[i]表示数组中小于等于i的数有多少个，
 * 则cnt[]数组随着数字i的逐渐增大具有单调性，即 target前，cnt[i] <= i, target后，cnt[i] > i
 */
public class FormalSolution2 {
    public static void main(String[] args) {
        FormalSolution2 solution2 = new FormalSolution2();
        int[] nums = {1,3,4,2,2};
        solution2.findDuplicate(nums);
    }
    public int findDuplicate(int[] nums) {
        int n = nums.length;
        int l = 1, r = n - 1, ans = -1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            int cnt = 0;
            for (int i = 0; i < n; ++i) {
                if (nums[i] <= mid) {
                    cnt++;
                }
            }
            if (cnt <= mid) {
                l = mid + 1;
            } else {
                r = mid - 1;
                ans = mid;
            }
        }
        return ans;
    }
}
